ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpd/walk/walk.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4 #include <cassert>
   5 #include <cstdio>
   6
   7 using namespace std;
   8
   9 typedef pair<int, int> Coord;
  10 typedef vector<Coord> Poly;
  11
  12 #define x       first
  13 #define y       second
  14
  15 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  16 #define forn(i, n)      forsn (i, 0, n)
  17
  18 #define coord_sub(c1, c2)       Coord((c1).x - (c2).x, (c1).y - (c2).y)
  19
  20 bool cross_prod_sign(const Coord& p, const Coord& q) {
  21     const long long int pxqy = ((long long int)p.x) * q.y;
  22     const long long int qxpy = ((long long int)q.x) * p.y;
  23     return pxqy >= qxpy;
  24 }
  25
  26 bool se_cruzan(const Coord& s0, const Coord& s1, const Coord& t0, const Coord& t1) {
  27 #define se_cruzan1(a, b, c, d) (cross_prod_sign(coord_sub(a, c), coord_sub(d, c)) != cross_prod_sign(coord_sub(b, c), coord_sub(d, c)))
  28     return se_cruzan1(s0, s1, t0, t1) && se_cruzan1(t0, t1, s0, s1);
  29 #undef se_cruzan1
  30 }
  31
  32 bool esta_adentro(const Coord& punto, const Poly& poly) {
  33     // buscar un punto afuera
  34     int maxx = punto.x;
  35     forn (i, (int)poly.size()) {
  36         maxx = max(maxx, poly[i].x);
  37     }
  38     maxx++;
  39     const Coord externo(maxx, punto.y + 1);
  40
  41     // ver si la cantidad de cruces es par o impar
  42     const int n = poly.size();
  43     bool adentro = false;
  44     forn (i, n) adentro ^= se_cruzan(punto, externo, poly[i], poly[(i + 1) % n]);
  45     return adentro;
  46 }
  47
  48 long long int doble_area(const Poly& poly) {
  49     const int n = poly.size();
  50     long long int s = 0;
  51     forn (i, n) {
  52         const int j = (i + 1) % n;
  53         s += ((long long int)poly[i].x) * poly[j].y - ((long long int)poly[i].y) * poly[j].x;
  54     }
  55     return s < 0 ? -s : s;
  56 }
  57
  58 typedef vector<int> vint;
  59 typedef vector<long long int> vllint;
  60
  61 vllint __area2;
  62 bool cmp_area2(int i, int j) {
  63     return __area2[i] < __area2[j];
  64 }
  65 void minwalk(const vector<int>& heights, const vector<Poly>& curves, const Coord& pos_alice, const Coord& pos_bob) {
  66     const int n = curves.size();
  67
  68     // ordenar los poligonos por area
  69     __area2 = vllint(n);
  70     forn (pi, n) {
  71         __area2[pi] = doble_area(curves[pi]);
  72     }
  73     vint ind(n, 0);
  74     forn (i, n) ind[i] = i;
  75     sort(ind.begin(), ind.end(), cmp_area2);
  76
  77     // visitarlos en ese orden y calcular cuanto sube / baja
  78 #define up_down(H1, H2) if (H1 < H2) { cost_up += H2 - H1; } else { cost_down += H1 - H2; }
  79     int last_height_alice = -1, last_height_bob = -1;
  80     int cost_up = 0, cost_down = 0;
  81     forn (i, n) {
  82         const int j = ind[i];
  83         const bool contains_alice = esta_adentro(pos_alice, curves[j]);
  84         const bool contains_bob = esta_adentro(pos_bob, curves[j]);
  85         if (contains_alice && contains_bob) {
  86             break;
  87         } else if (contains_alice) {
  88             if (last_height_alice != -1) {
  89                 up_down(last_height_alice, heights[j]);
  90             }
  91             last_height_alice = heights[j];
  92         } else if (contains_bob) {
  93             if (last_height_bob != -1) {
  94                 up_down(heights[j], last_height_bob);
  95             }
  96             last_height_bob = heights[j];
  97         }
  98     }
  99     if (last_height_alice != -1 && last_height_bob != -1) {
 100         up_down(last_height_alice, last_height_bob);
 101     }
 102     printf("%i %i\n", cost_up, cost_down);
 103 }
 104
 105 int main() {
 106     const Coord pos_alice(0, 0);
 107     const Coord pos_bob(100000, 0);
 108     int ncases;
 109     scanf("%i\n", &ncases);
 110     forn (ci, ncases) {
 111         int npolys;
 112         scanf("%i\n", &npolys);
 113
 114         vector<Poly> polys;
 115         vector<int> heights;
 116         forn (pi, npolys) {
 117             int curve_height, nverts;
 118             scanf("%i %i", &curve_height, &nverts);
 119             polys.push_back(Poly());
 120             forn (vi, nverts) {
 121                 int vert_x, vert_y;
 122                 scanf("%i %i", &vert_x, &vert_y);
 123                 polys[pi].push_back(Coord(vert_x, vert_y));
 124             }
 125             heights.push_back(curve_height);
 126         }
 127
 128         minwalk(heights, polys, pos_alice, pos_bob);
 129     }
 130     return 0;
 131 }
 132